In an interconnected computer network, the devices communicate through transactions. A transaction comprises one or more packets and conveys some meaningful information. For example, a CPU in a multiprocessor network may respond to a snoop request with a "snoop response" transaction. Generally, a packet consists of a fixed number of transfers or cycles in the interconnect structure. Different transactions may require different numbers of packets.
The flow of the different types of transactions is controlled by ordering constraints. These constraints specify the ordering relationship of every transaction with respect to others. A certain transaction type may be required to bypass other transaction types to guarantee forward progress, and the certain transaction types may be forbidden to bypass some other transaction types to guarantee ordering. Typically, these ordering rules are provided by an ordering table which specifies the ordering relationship between every pair of transaction types.
For any pair of transaction types P and Q, the ordering table specifies if P should bypass Q or if P should not bypass Q or if it does not matter if P bypasses Q. Similarly, another entry in the table would specify if Q could bypass P. An example of ordering constraints can be found in the ordering table in the PCI bus specification, PCI Local Bus Specification, Rev. 2.1, PCI Special Interest Group, Portland, OR, June 1995. These ordering rules are traditionally implemented by loading all incoming transactions to a common queue. A bypassable transaction is subsequently loaded to a separate bypass queue (or a system of queues) when it moves to the head of the common queue.
FIG. 4 depicts a typical prior art arrangement 40 for implementing a subset of PCI transactions on a PCI to PCI bridge 41 connecting two PCI buses, bus A 42 and B 43. This arrangement would handle two types of PCI transactions, the posted memory write (PMW) and the delayed read request (DRR). A PMW transaction is required to bypass earlier DRR transactions to avoid deadlock. However, a DRR transaction is not allowed to bypass PMW transactions to enforce the ordering model. Transactions arriving at PCI bus bridge 41 from PCI bus A 42, need to be queued in such a way that these ordering restrictions are maintained. Thus, this approach uses two queues, a bypass queue 44 for DRR transactions only, and a common queue 45 where both PMW and DRR transactions are loaded. Both DRR and PMW transactions are stored into common queue 45 from PCI bus A. When a DRR transaction gets to the head of common queue 45, it is then loaded to the bypass DRR queue 44. Thus, if there are any PMWs after the DRR, they can bypass the DRR and be sent out over PCI bus B 43. The DRR will be sent out after all of the PMWs have been sent out.
A problem with this arrangement is that although it meets the ordering requirements of the PCI specification, it degrades performance by not fully utilizing the available bandwidth of PCI bus B 43. The under utilization of the PCI bus B arises when a DRR transaction is loaded to the bypass queue from the common queue. Being a FIFO structure, the common queue cannot unload a subsequent PMW transaction to the PCI bus B when a DRR transaction at its head is being unloaded to the bypass queue. Thus, the prior art arrangement is not able to achieve the maximum bandwidth available on the PCI bus B.
Another problem with this arrangement is that the common queue must be of a large size. Certain types of large transactions require a large amount of storage space. Ideally, these large transactions would not be queued, but would rather be sent immediately over the bus. However, to maintain ordering, these transactions must be able to fit into the common queue along with the other transactions.
Therefore, there is a need in the art for a mechanism which will eliminate this performance bottleneck, while still maintain ordering, and reducing the required size of the common queue.